Attualmente sto scrivendo un parser di base per un gusto XML. Come esercizio, sto implementando un parser basato su tabella LL. Questo è il mio esempio di grammatica BNF: % stringa di dati nome token %% / * LL (1) * / doc: elem elem: "<" open_tag open_tag: nome attr close_tag close_tag: ">" elem_or_data "" | "/>" ; elem_or_data: "<" open_tag elem_or_data | data elem_or_data | / * epsilon * / ; attr: nome ":" stringa attr | / * epsilon * / ; Questa grammatica è corretta? Ogni letterale terminale è tra virgolette. I terminali astratti sono specificati da% token. Sto codificando un lexer scritto a mano per convertire il mio input in un elenco di token. Come tokenizzerei i terminali astratti?
2021-03-03 08:10:57
L'approccio classico sarebbe scrivere un'espressione regolare (o un altro riconoscitore) per ogni possibile terminale.
Ciò che chiamate terminali "astratti", che sono perfettamente concreti, sono in realtà terminali i cui pattern associati riconoscono più di una possibile stringa di input. La stringa effettivamente riconosciuta (o qualche funzione calcolata di quella stringa) dovrebbe essere passata al parser come valore semantico del token.
Nominalmente, in ogni punto della stringa di input, il tokeniser eseguirà tutti i riconoscitori e sceglierà quello con la corrispondenza più lunga. (Questa è la cosiddetta regola del "munch massimo".) Di solito può essere ottimizzata, in particolare se tutti i pattern sono espressioni regolari. (F) lex farà questa ottimizzazione per te, per esempio.
Una complicazione nel tuo caso è che la tokenizzazione della tua lingua dipende dal contesto. In particolare, quando il target è elem_or_data, gli unici token possibili sono <,